`
https://leetcode.cn/problems/maximum-subarray/
`

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  const n = nums.length
  // 构建前缀和数组
  const prefix = new Array(n + 1).fill(0)
  for (let i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + nums[i - 1]
  }

  let minVal = Infinity
  let res = -Infinity

  for (let i = 0; i < n; i++) {
    // 维护 minVal 是 prefix[0..i] 的最小值
    minVal = Math.min(minVal, prefix[i])
    // 以 nums[i] 结尾的最大子数组和就是 prefix[i+1] - min(prefix[0..i])
    res = Math.max(res, prefix[i + 1] - minVal)
  }
  return res
};